785. Is Graph Bipartite?
Medium

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

  • There are no self-edges (graph[u] does not contain u).
  • There are no parallel edges (graph[u] does not contain duplicate values).
  • If v is in graph[u], then u is in graph[v] (the graph is undirected).
  • The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

 

Example 1:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

Example 2:

Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.

 

Constraints:

  • graph.length == n
  • 1 <= n <= 100
  • 0 <= graph[u].length < n
  • 0 <= graph[u][i] <= n - 1
  • graph[u] does not contain u.
  • All the values of graph[u] are unique.
  • If graph[u] contains v, then graph[v] contains u.
Accepted
203,950
Submissions
416,279
Seen this question in a real interview before?
Companies

Average Rating: 4.55 (66 votes)

Premium

Approach #1: Coloring by Depth-First Search [Accepted]

Intuition

Color a node blue if it is part of the first set, else red. We should be able to greedily color the graph if and only if it is bipartite: one node being blue implies all it's neighbors are red, all those neighbors are blue, and so on.


Diagram of coloring neighbors of nodes

Algorithm

We'll keep an array (or hashmap) to lookup the color of each node: color[node]. The colors could be 0, 1, or uncolored (-1 or null).

We should be careful to consider disconnected components of the graph, by searching each node. For each uncolored node, we'll start the coloring process by doing a depth-first-search on that node. Every neighbor gets colored the opposite color from the current node. If we find a neighbor colored the same color as the current node, then our coloring was impossible.

To perform the depth-first search, we use a stack. For each uncolored neighbor in graph[node], we'll color it and add it to our stack, which acts as a sort of "todo list" of nodes to visit next. Our larger loop for start... ensures that we color every node. Here is a visual dry-run of the algorithm whose Python code is below.

Complexity Analysis

  • Time Complexity: O(N+E)O(N + E), where NN is the number of nodes in the graph, and EE is the number of edges. We explore each node once when we transform it from uncolored to colored, traversing all its edges in the process.

  • Space Complexity: O(N)O(N), the space used to store the color.

Report Article Issue

Comments: 35
ursbhaskar's avatar
Read More

The problem is missing one specific information that the input can produce disconnected multiple graphs, which should be a huge point. I could not figure out why my answer was marked wrong until I looked up the solution.

Surprising thing is others providing answers as if that is not a concern.

67
Show 5 replies
Reply
Share
Report
Werber-Zeng's avatar
Read More

This is actually variant of Hungarian Algorithm.

26
Show 5 replies
Reply
Share
Report
Atoosa's avatar
Read More

Isn't this approach a BFS? The title says DFS, but I'm really confused as it appears to be BFS

33
Show 6 replies
Reply
Share
Report
calvinchankf's avatar
Read More

Similar logic. I did it in both BFS and the recursive DFS. Know both to crack the coding interviews.💪🏻

"""
    1st approach: BFS + nodes coloring

    Time    O(V+E)
    Space   O(V)
    156 ms, faster than 62.09%
"""


class Solution(object):
    def isBipartite(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: bool
        """
        seen = {}
        # we need to check every node because it is possible that graph[0] doesn't have any vertices connected
        for i in range(len(graph)):
            if i not in seen:
                if self.check(graph, i, seen) == False:
                    return False
        return True

    def check(self, graph, start, seen):
        q = [(start, 1)]
        while len(q) > 0:
            pop, color = q.pop(0)
            if pop in seen:
                if seen[pop] != color:
                    return False
                continue
            seen[pop] = color
            vertices = graph[pop]
            for v in vertices:
                q.append((v, -color))
        return True


"""
    2nd approach: recursive DFS + nodes coloring

    Time    O(V+E)
    Space   O(V)
    164 ms, faster than 40.67%
"""


class Solution(object):
    def isBipartite(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: bool
        """
        seen = {}
        # we need to check every node because it is possible that graph[0] doesn't have any vertices connected
        for i in range(len(graph)):
            if i not in seen:
                if self.check(graph, i, 1, seen) == False:
                    return False
        return True

    def check(self, graph, node, color, seen):
        if node in seen:
            if seen[node] != color:
                return False
            return True
        seen[node] = color
        vertices = graph[node]
        for v in vertices:
            if self.check(graph, v, -color, seen) == False:
                return False
        return True

BTW, here is another question we can use the similar approach, #886 , practice them in a row to get familiar with this type of questions

9
Show 1 reply
Reply
Share
Report
cpjo's avatar
Read More

Why do you use stack?

12
Show 9 replies
Reply
Share
Report
undefitied's avatar
Read More

Thanks for the article!
For some reason I assumed, that all nodes are connected, and started with a just queue(/stack), missing the first for-loop.

8
Reply
Share
Report
sschangi's avatar
Read More

So is there any difference between the time and space complexity of the DFS approach and the BFS approach?

7
Show 3 replies
Reply
Share
Report
cpshilpa's avatar
Read More

Could someone please explain how the graph is represented in the description. How does [[1,3], [0,2], [1,3], [0,2]] turn to
0----1
| |
| |
3----2

4
Show 3 replies
Reply
Share
Report
crisjul09's avatar
Read More

Here is the bfs and dfs solutions.
DFS:

class Solution {
    public boolean isBipartite(int[][] graph) {
        Set<Integer> A = new HashSet<>();
        Set<Integer> B = new HashSet<>();
        for (int i = 0; i < graph.length; i++) {
            if (!A.contains(i) && !B.contains(i)) {
                A.add(i);
                if (!dfs(graph, i, A, B)) {
                    return false;
                }
            }
        }
        return true;
    }
    
    boolean dfs(int[][] graph, int node, Set<Integer> A, Set<Integer> B) {
        for (int i = 0; i < graph[node].length; i++) {
            if (!A.contains(graph[node][i]) && !B.contains(graph[node][i])) {
                if (A.contains(node)) {
                    B.add(graph[node][i]);
                }
                else {
                    A.add(graph[node][i]);
                }
                if (!dfs(graph, graph[node][i], A, B)) {
                    return false;
                }                
            }
            else {
                if ((A.contains(node) && A.contains(graph[node][i])) || (B.contains(node) && B.contains(graph[node][i]))) {
                    return false;
                }
            }
        }
        return true;
    }
}

BFS:

class Solution {
    public boolean isBipartite(int[][] graph) {
        int[] color = new int[graph.length];
        Arrays.fill(color, -1);
        for (int i = 0; i < graph.length; i++) {
            if (color[i] == -1 && !bfs(graph, color, i)) {
                return false;
            }
        }
        return true;
    }
    
    boolean bfs(int[][] graph, int[] color, int node) {
        Queue<Integer> queue = new LinkedList<Integer>();
        color[node] = 0;
        queue.add(node);
        while (!queue.isEmpty()) {
            int n = queue.poll();
            for (int i = 0; i < graph[n].length; i++) {
                if (color[graph[n][i]] == -1) {
                    color[graph[n][i]] = color[n] ^ 1;
                    queue.add(graph[n][i]);
                }
                else {
                    if (color[graph[n][i]] == color[n]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

4
Show 1 reply
Reply
Share
Report
thegreenquaga's avatar
Read More

There is no need to create new stack for every iteration.

3
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
04/23/2021 12:47Accepted20 ms13.5 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.